package leetcode_day._2021._202105._1120;

import java.util.Arrays;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/5/11 22:47
 * 解码异或后的排列
 * 算法：位运算
 * 数组是由 1 ~ n 组成的
 * 由于 n 是偶数
 * 所以加密之后有 n - 1 个元素
 * 把加密后的数组从下标 0 开始，隔着 1 个异或
 * 可以得出 1 ~ n - 1 的异或
 * 再计算 1 ~ n 的异或值
 * 这两个结果异或，可以得出最后一个元素的值
 */
public class _11_1734 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new _11_1734().decode(new int[]{3, 1})));
    }

    public int[] decode(int[] encoded) {
        int n = encoded.length + 1;
        int[] ans = new int[n];
        int last = 0;
        for (int i = 0; i < encoded.length; i += 2) last ^= encoded[i];
        for (int i = 1; i <= n; ++i) last ^= i;
        ans[n - 1] = last;
        System.out.println(n - 2);
        for (int i = n - 2; i >= 0; i--) ans[i] = ans[i + 1] ^ encoded[i];
        return ans;
    }
}
